#ifndef SAT_H
#define SAT_H

#include <iostream>  
#include <vector>  
#include <cmath>  
#include <limits>  

class Vector {  
public:  
    float X;  
    float Y;  
  
    Vector(float x, float y) : X(x), Y(y) {}
    Vector() {}   
  
    Vector operator-(const Vector& other) const {  
        return Vector(X - other.X, Y - other.Y);  
    }  
    
     Vector operator*(float scalar) const {
        return Vector(X * scalar, Y * scalar);
    }

    static float Dot(const Vector& a, const Vector& b) {  
        return a.X * b.X + a.Y * b.Y;  
    }  
    
    Vector operator+(const Vector& other) const {
        return Vector(X + other.X, Y + other.Y);
    }
    static Vector Perpendicular(const Vector& v) {  
        return Vector(-v.Y, v.X); // 顺时针旋转90度  
    }  
};  
  
class Polygon {  
public:  
    std::vector<Vector> Vertices;  
  
    Polygon() {}  
    Polygon(const std::vector<Vector>& vertices) : Vertices(vertices) {}  
  
    std::vector<Vector> GetEdges() const {  
        std::vector<Vector> edges;  
        for (size_t i = 0; i < Vertices.size(); ++i) {  
            Vector start = Vertices[i];  
            Vector end = Vertices[(i + 1) % Vertices.size()];  
            edges.push_back(end - start);  
        }  
        return edges;  
    }  
  
    std::vector<Vector> GetNormals() const {  
        std::vector<Vector> normals;  
        for (const Vector& edge : GetEdges()) {  
            normals.push_back(Vector::Perpendicular(edge));  
        }  
        return normals;  
    }  
  
    std::vector<float> ProjectOntoAxis(const Vector& axis) const {  
        float min = std::numeric_limits<float>::max();  
        float max = std::numeric_limits<float>::lowest();  
  
        for (const Vector& vertex : Vertices) {  
            float projection = Vector::Dot(vertex, axis);  
            min = std::min(min, projection);  
            max = std::max(max, projection);  
        }  
  
        return {min, max};  
    }  
};  
  
typedef struct {
    Polygon poly;
    uint8_t wp;
} NonRecognitionAreaAttr;
// std::vector<bbox_t> WarningAreabox;
extern std::vector<NonRecognitionAreaAttr> NoRecognitionAreaAttrs;
// std::atomic<bool> save_WarningArea_state{false};

class SAT {  
public:  
    static bool ArePolygonsIntersecting(const Polygon& polyA, const Polygon& polyB) {  
        for (const Vector& normal : polyA.GetNormals()) {  
            if (!IsProjectionOverlapping(polyA, polyB, normal)) {  
                return false;  
            }  
        }  
  
        for (const Vector& normal : polyB.GetNormals()) {  
            if (!IsProjectionOverlapping(polyA, polyB, normal)) {  
                return false;  
            }  
        }  
  
        return true; // 如果在所有轴投影上都有重叠，则多边形相交  
    }  

    static bool IsPolygonContainsBbox(const Polygon& container, const Polygon& target) {
        
        std::cout << "In IsPolygonContainsBbox:----------------" << std::endl;
        // 先检查所有顶点是否在容器多边形内
        for (const auto& vertex : target.Vertices) {
            std::cout << "vertex: " << vertex.X << " " << vertex.Y << std::endl;
            if (!IsPointInPolygon(container, vertex)) {
                return false;
            }
        }
        // 再检查是否没有边相交（避免穿透情况）
        return !ArePolygonsIntersecting(container, target);
    }
  
private:  
    static bool IsProjectionOverlapping(const Polygon& polyA, const Polygon& polyB, const Vector& axis) {  
        std::vector<float> aProjections = polyA.ProjectOntoAxis(axis);
        std::vector<float> bProjections = polyB.ProjectOntoAxis(axis);

        float aMin = aProjections[0];
        float aMax = aProjections[1];
        float bMin = bProjections[0];
        float bMax = bProjections[1];
  
        return aMax >= bMin && bMax >= aMin; // 重叠条件  
    }  

    static bool IsPointInPolygon(const Polygon& poly, const Vector& point) {

        std::cout << "In IsPointInPolygon:------------" << std::endl;
        int crossings = 0;
        const auto& vertices = poly.Vertices;
        
        for (size_t i = 0; i < vertices.size(); ++i) {
            const Vector& v1 = vertices[i];
            const Vector& v2 = vertices[(i+1)%vertices.size()];
            
            // 射线与边交点的Y坐标判断
            if ((v1.Y <= point.Y && v2.Y > point.Y) || 
                (v1.Y > point.Y && v2.Y <= point.Y)) {
                float t = (point.Y - v1.Y) / (v2.Y - v1.Y);
                float xIntersect = v1.X + t * (v2.X - v1.X);
                
                if (point.X < xIntersect) {
                    crossings++;
                }
            }
        }
        std::cout << "crossings: " << crossings << std::endl;
        return (crossings % 2) == 1;
    }
};  

// 分解凹多边形的类  
class MyConcavePolygonDecomposer {  
public:  
    // 分解凹多边形的方法  
    static std::vector<std::vector<Vector>> DecomposeConcavePolygon(const std::vector<Vector>& polygon) {  
        std::vector<std::vector<Vector>> convexPolygons;  
  
        // 继续分解直到没有凹角  
        std::vector<Vector> tempPolygon = polygon;  
        while (HasConcaveAngle(tempPolygon)) {  
            std::vector<Vector> convexPolygon;  
            // 选择一个凹角并绘制对角线  
            for (size_t i = 0; i < tempPolygon.size(); ++i) {  
                if (IsConcave(tempPolygon, i)) {  
                    // 找到凹角的相邻顶点  
                    size_t prevIndex = (i - 1 + tempPolygon.size()) % tempPolygon.size();  
                    size_t nextIndex = (i + 1) % tempPolygon.size();  
  
                    // 绘制对角线并更新多边形  
                    convexPolygon.push_back(tempPolygon[prevIndex]);  
                    convexPolygon.push_back(tempPolygon[i]);  
                    convexPolygon.push_back(tempPolygon[nextIndex]);  
  
                    // 更新原多边形  
                    tempPolygon.erase(tempPolygon.begin() + i);  
                    break; // 重新开始外层循环  
                }  
            }  
            convexPolygons.push_back(convexPolygon);  
        }  
  
        // 添加剩余的凸多边形  
        if (!tempPolygon.empty()) {  
            convexPolygons.push_back(tempPolygon);  
        }  
  
        return convexPolygons;  
    }  
  
    // 检查多边形是否有凹角  
    static bool HasConcaveAngle(const std::vector<Vector>& polygon) {  
        for (size_t i = 0; i < polygon.size(); ++i) {  
            if (IsConcave(polygon, i)) {  
                return true;  
            }  
        }  
        return false;  
    }  
  
    // 判断给定顶点是否为凹角  
    static bool IsConcave(const std::vector<Vector>& polygon, size_t index) {  
        size_t prevIndex = (index - 1 + polygon.size()) % polygon.size();  
        size_t nextIndex = (index + 1) % polygon.size();  
  
        // 计算向量  
        Vector v1 = {polygon[nextIndex].X - polygon[index].X, polygon[nextIndex].Y - polygon[index].Y};  
        Vector v2 = {polygon[prevIndex].X - polygon[index].X, polygon[prevIndex].Y - polygon[index].Y};  
  
        // 计算叉积  
        double crossProduct = v1.X * v2.Y - v1.Y * v2.X;  
  
        // 如果叉积小于0，则为凹角  
        return crossProduct < 0;  
    } 
     
};  

#endif